package sort;

public class QuickSort {

    public static void sort(int[] arrSrc) {
        sortRecursion(arrSrc, 0, arrSrc.length - 1);
    }

    private static void sortRecursion(int[] arrSrc, int iStartPos, int iEndPos) {
        if (iStartPos >= iEndPos) {
            return;
        }

        //获得中间点后，将其分为三个部分，进行递归
        int iPivot = getPivot(arrSrc, iStartPos, iEndPos);
        sortRecursion(arrSrc, iStartPos, iPivot - 1);
        sortRecursion(arrSrc, iPivot + 1, iEndPos);
    }

    //比较排序后得到中间点
    private static int getPivot(int[] arrSrc, int iStart, int iEnd) {
        //每次将最后一位作为比较点
        int iPivot = arrSrc[iEnd];
        int i = iStart;//记录比最后一位大的数据位置
        int j = iStart;//记录比最后一位小的数据位置

        for (; j < iEnd; j++) {

            //当前的点若比最后一位数小，则与之前比最后一位大的进行数据交换
            if (arrSrc[j] < iPivot) {
                int iTemp = arrSrc[i];
                arrSrc[i] = arrSrc[j];
                arrSrc[j] = iTemp;
                i++;//交换后记得将其下标向后移动一位
            }
        }

        //最后进行一次数据交换
        int iTemp = arrSrc[i];
        arrSrc[i] = arrSrc[iEnd];
        arrSrc[iEnd] = iTemp;

        return i;
    }

    public static void main(String[] args) {
        int[] arrSrc = CommonUtil.createIntArray(20);
        CommonUtil.printArr(arrSrc);
        sort(arrSrc);
        CommonUtil.printArr(arrSrc);
    }
}
